//我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 
//
// 
//
// 示例: 
//
// 输入: n = 10
//输出: 12
//解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 
//
// 说明: 
//
// 
// 1 是丑数。 
// n 不超过1690。 
// 
//
// 注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/ 
// Related Topics 哈希表 数学 动态规划 堆（优先队列） 👍 353 👎 0

package leetcode.editor.cn;

import java.util.HashSet;
import java.util.PriorityQueue;

//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer49 {
    /**
     * 方法1：堆
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> queue = new PriorityQueue<>(((o1, o2) -> o1.compareTo(o2)));
        HashSet<Long> set = new HashSet<>();
        int[] factors = {2,3,5};
        queue.offer(1L);
        set.add(1L);
        while(!queue.isEmpty()){
            long num = queue.poll();
            if(--n == 0) return (int) num;
            for(int factor : factors){
                long next = factor * num;
                if(set.add(next)){
                    queue.offer(next);
                }
            }
        }
        //写法冗余
//        while(!queue.isEmpty()){
//            long num = queue.poll();
//            n--;
//            if(n == 0) return (int)num;
//            if(!set.contains(2*num)){
//                set.add(2*num);
//                queue.offer(2*num);
//            }
//            if(!set.contains(3*num)){
//                set.add(3*num);
//                queue.offer(3*num);
//            }
//            if(!set.contains(5*num)){
//                set.add(5*num);
//                queue.offer(5*num);
//            }
//        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
